[BAEKJOON] 16681. 등산

Posted on September 12, 2021

문제 :

주환이는 요즘 등산에 빠졌다. 주환이는 등산을 위해 지도를 가지고 있는데, 그 지도에는 각 지점의 높이와 갈 수 있는 다른 지점까지의 거리가 표시되어 있다.

주환이는 아침에 집에서 출발하여 등산을 갔다가, 오후 수업을 듣기 위해 고려대학교로 돌아와야 한다.

주환이는 지도의 임의의 지점을 골라, 그 지점을 목표로 정한다. 집 또는 고려대학교는 목표로 선택할 수 없다.
주환이가 집에서 정한 목표에 도달할 때 까지는 항상 높이가 증가하는 방향으로만 이동해야 한다.
주환이가 정한 목표에 도달한 후, 고려대학교로 갈 때에는 항상 높이가 감소하는 방향으로만 이동해야 한다.
주환이는 거리 1을 움직일 때 마다 D 의 체력이 소모된다.
주환이는 정한 목표에 도달하면 높이 1당 E 의 성취감을 얻는다. 즉 높이가 h인 목표에 도달하면 hE의 성취감을 얻는다.

주환이는 이 등산의 가치를 (얻은 성취감) - (소모한 체력) 으로 계산하기로 하였다. 주환이를 위해 가치가 가장 높은 등산 경로를 선택해주자.

입력 :

첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 100,000, 1 ≤ M ≤ 200,000, 1 ≤ D ≤ 100, 1 ≤ E ≤ 100)

두 번째 줄에 N개의 정수 h1, … ,hN이 공백으로 구분되어 주어진다. hi는 i 번째 지점의 높이를 의미한다. (1 ≤ hi ≤ 1,000,000, 1 ≤ i ≤ N)

세 번째 줄부터 M개의 줄에 걸쳐 세 정수 a, b, n이 공백으로 구분되어 주어진다. 이는 a번 지점과 b번 지점을 잇는 거리 n의 양방향 경로가 있음을 의미한다. (1 ≤ a, b ≤ N, 1 ≤ n ≤ 100,000)

어떤 지점에서 다른 지점으로 가는 경로가 여러 개 있을 수도 있으며 (등산로는 여러 개가 있을 수 있다), 한 지점에서 출발해 그 지점으로 돌아가는 경로가 있을 수도 있다 (쉼터에서 몇 바퀴 돌며 쉴 수도 있다).

주환이의 집은 1번 지점에 위치하고, 고려대학교는 N번 지점에 위치하며 주환이의 집과 고려대학교의 높이는 1임이 보장된다.

출력 :

첫 번째 줄에 주환이가 얻을 수 있는 가치의 최댓값을 출력한다. 만약 조건을 만족하는 등산 경로를 선택할 수 없다면, ”Impossible“을 쌍따옴표를 제외하고 출력한다. 답이 음수일 수 있음에 유의하여라.

풀이 :

지점과 경로가 많은 갯수로 얽혀있으며 높이와 거리를 모두 고려해주어야 하기 때문에 자칫 어려워 보일 수 있으나, 결론적으로 풀이 방식은 크게 어렵지 않았다.

가장 중요한 key point는 각 지점별 집 -> (해당 지점) 까지 최소 거리 오르막길, (해당 지점) -> 고려대 까지의 최소 거리 내리막길을 각각 구해주어야 한다.

각 지점별 최소 거리 오르막길과 내리막길은 우선순위 큐를 활용해서 다익스트라 알고리즘을 활용해준다.
오르막길과 내리막길은 비슷한 과정이 반복되는 코드이기 때문에 calculMinDist() 함수로 통합해 구현해준다. (내리막길을 고려대 -> (특정 지점) 과 같이 오르막길로 가정하고 구현해주면 가능하다.)

이렇게 구한 내리막길과 오르막길의 최소 거리를 통해 최대 가치를 (성취감 단위) * (해당 지점 높이) - (해당 지점 오르막 최소 거리 + 해당 지점 내리막 최소 거리) * (체려 소모 단위) 식으로 구한다.

코드 :

코드 보기/접기

#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <algorithm>

#define ll long long
#define MAX 1987654321987654321
#define MIN -1987654321987654321
#define pii pair<int, int>
#define pli pair<ll, int>

using namespace std;
int n, m, consume, energy;
vector<int> heights;
vector<vector<pii>> adj;

void inputProcess() {
    int fir, sec, dist;
    cin >> n >> m >> consume >> energy;

    heights.resize(n + 1);
    adj.resize(n + 1);

    for (int k = 1; k <= n; k++) {
        cin >> heights[k];
    }

    while (m--) {
        cin >> fir >> sec >> dist;
        adj[fir].emplace_back(sec, dist);
        adj[sec].emplace_back(fir, dist);
    }
}

void calculMinDist(int startIdx, vector<ll> *minDist) {
    priority_queue<pli, vector<pli>> pq;

    (*minDist)[startIdx] = 0;
    pq.push(pli(0, startIdx));

    while (!pq.empty()) {
        ll curDist = pq.top().first;
        int curIdx = pq.top().second;
        pq.pop();
        if ((*minDist)[curIdx] < curDist) continue;

        int size = adj[curIdx].size();
        for (int t = 0; t < size; t++) {
            int nextIdx = adj[curIdx][t].first;
            ll nextDist = adj[curIdx][t].second;
            if (heights[nextIdx] <= heights[curIdx]) continue;

            ll distSum = curDist + nextDist;
            if ((*minDist)[nextIdx] > distSum) {
                (*minDist)[nextIdx] = distSum;
                pq.push(pli(distSum, nextIdx));
            }
        }
    }
}

int main() {
    ll answer = MIN;
    vector<ll> ascDist, descDist;

    inputProcess();
    ascDist.resize(n + 1, MAX);
    descDist.resize(n + 1, MAX);

    calculMinDist(1, &ascDist);
    calculMinDist(n, &descDist);

    for (int k = 2; k < n; k++) {
        if (ascDist[k] == MAX || descDist[k] == MAX)
            continue;

        answer = max(answer, heights[k] * energy - (ascDist[k] + descDist[k]) * consume);
    }

    if (answer == MIN) {
        cout << "Impossible\n";
    } else {
        cout << answer << '\n';
    }

    return 0;
}

Algorithm

algorithm baekjoon C++